/*
 * @lc app=leetcode.cn id=1575 lang=typescript
 *
 * [1575] 统计所有可行路径
 */

// @lc code=start
function countRoutes(locations: number[], start: number, finish: number, fuel: number): number {
  const mod = 1e9 + 7;
  const n = locations.length;
  // f[i][j] 表示从 i 到终点剩余 j 油量的方法数
  const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(fuel + 1).fill(-1));
  // 计算过程
  const getResult = (s: number, e: number, r: number): number => {
    // 如果已经计算过，直接返回
    if (f[s][r] !== -1) return f[s][r];
    // 如果起点终点相同，最少有 1 个方法
    if (s === e) f[s][r] = 1;
    // 如果起点终点不同，方法数为 0
    else f[s][r] = 0;

    for (let i = 0; i < n; i++) {
      // 起点相同，跳过
      if (s === i) continue;
      // 如果 s 到 i 的距离大于剩余油量，跳过
      const diff = Math.abs(locations[s] - locations[i]);
      if (diff > r) continue;
      // 更新方法数
      f[s][r] += getResult(i, e, r - diff);
      f[s][r] %= mod;
    }

    return f[s][r];
  };

  return getResult(start, finish, fuel);
}
// @lc code=end
